package com.jz.algorithm.BinarySearch;

/**
 * @Classname BinarySearch
 * @Description 二分法相关题目
 * @Date 2021/10/19 14:44
 * @Author Jz
 * @Version 1.0
 */
public class BinarySearch {

    /**
     * @Methodname binarySearch
     * @Description TODO
     * @Date 2021/10/19 14:44
     * @Created Jz
     * @Return 下标位置
     * @Param array数组 最左边位置，最右边位置，目标值
     */
    public static int binarySearch(int[] array, int left, int right, int n) {

        int middle = 0;
        while (left < right) {
            middle = left + (right - left / 2);
            if (array[middle] == n) {
                return middle;
            } else if (array[middle] > n) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }


        return middle;
    }

    /**
     * @Methodname searchInsert leetcode 35
     * @Description TODO
     * @Date 2021/10/25 16:31
     * @Author Jz
     * @Return 目标位置
     * @Param nums数组 target目标值 z
     */
    public static int searchInsert(int[] nums, int target) {

        int middle = 0;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            middle = (right + left) / 2;
            if (nums[middle] == target) {
                return middle;
            } else if (nums[middle] > target) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }


        return left;
    }

    /**
     * @Methodname searchRange
     * @Description 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
     * 如果数组中不存在目标值 target，返回 [-1, -1]。
     * @Date 2021/10/25 17:54
     * @Author Jz
     * @Return
     * @Param
     */
    public static int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) {
            return new int[]{-1, -1};
        }

        int middle = 0;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            middle = (right + left) / 2;
            if (nums[middle] == target) {
                break;
            } else if (nums[middle] > target) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        int end = middle;
        int start = middle;

        if (nums[middle] == target) {
            while (end <= nums.length - 1 && nums[end] == target) {
                end++;
            }

            while (start >= 0 && nums[start] == target) {
                start--;
            }
            return new int[]{start + 1, end - 1};
        } else {
            return new int[]{-1, -1};
        }


    }


    /**
     * @Methodname mySqrt
     * @Description 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
     * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
     * @Date 2021/10/26 10:08
     * @Author Jz
     * @Return x的算术平方根
     * @Param 输入值
     */
    public static int mySqrt(int x) {


        int left = 0;
        int right = x;
        while (left <= right) {
            int m = (left + right) / 2;
            int tem = m * m;
            if (tem == x) {
                return m;
            } else if (tem > x) {
                right = m - 1;
            } else {
                left = m + 1;
            }
        }
        return right;


    }

    /**
     * @Methodname 第二种解法
     * @Description TODO
     * @Date 2021/10/26 11:44
     * @Author Jz
     * @Return
     * @Param
     */
    static int s;

    public static int mySqrt1(int x) {
        s = x;
        if (x == 0) {
            return 0;
        }
        return ((int) (sqrts(x)));
    }

    public static double sqrts(double x) {
        double res = (x + s / x) / 2;
        if (res == x) {
            return x;
        } else {
            return sqrts(res);
        }
    }

    /**
     * @Methodname 第二种解法
     * @Description TODO
     * @Date 2021/10/26 11:44
     * @Author Jz
     * @Return
     * @Param
     */
    public static double mySqrt2(double x, int s1) {
        if (s1 == 0) {
            return 0;
        }
        double res = (x + s1 / x) / 2;
        if (res == x) {
            return x;
        } else {
            return mySqrt2(res, s1);
        }
    }

    /**
     * @Methodname isPerfectSquare
     * @Description 给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false
     * @Date 2021/10/26 13:23
     * @Author Jz
     * @Return true 代表是完全平方数 fasle 代表不是；
     * @Param 数组
     */
    public static boolean isPerfectSquare(int num) {

        double v = mySqrt2(24564, num);
        int v2 = (int) v;
        if (v - v2 != 0) {
            return false;

        } else {
            return true;
        }
    }

    /**
     * @Methodname generateMatrix
     * @Description 给定一个随机数n 生成一个 n*n的矩阵
     * @Date 2021/11/4 9:38
     * @Author Jz
     * @Return
     * @Param
     */
    public int[][] generateMatrix(int n) {

        return null;

    }






}
